package com.javaDemo.ti;

import java.util.LinkedList;

/**
 * 字符串解码器
 * 
 * @author csy
 * @date 2020/5/28 01:08
 * @description 解码规则：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次
 * 
 *              解题思路：
 *              1. 使用两个栈分别存储：
 *              - 数字栈：存储重复次数
 *              - 字符串栈：存储待拼接的字符串
 *              2. 遍历字符串，根据不同字符类型进行处理：
 *              - 数字：累积计算重复次数
 *              - '['：将当前重复次数和字符串入栈，重置计数器和结果串
 *              - ']'：出栈并进行字符串重复拼接
 *              - 字母：直接追加到结果串
 * 
 *              时间复杂度：O(n)，其中n为字符串长度
 *              空间复杂度：O(n)，栈的开销
 * 
 *              示例：
 *              输入：3[a]2[bc]
 *              输出：aaabcbc
 *              解释：3[a] = aaa，2[bc] = bcbc，最终 aaa + bcbc = aaabcbc
 */
public class StringDecoder {

    /**
     * 解码字符串
     * 
     * @param encodedString 编码后的字符串
     * @return 解码后的字符串
     */
    public static String decode(String encodedString) {
        if (encodedString == null || encodedString.isEmpty()) {
            return "";
        }

        // 存储重复次数的栈
        LinkedList<Integer> repeatCountStack = new LinkedList<>();
        // 存储中间结果的栈
        LinkedList<String> resultStack = new LinkedList<>();
        // 当前构建的字符串
        StringBuilder currentString = new StringBuilder();
        // 当前数字（重复次数）
        int currentNumber = 0;

        // 遍历每个字符
        for (char c : encodedString.toCharArray()) {
            if (c == '[') {
                // 遇到左括号，保存当前状态并重置
                repeatCountStack.addLast(currentNumber);
                resultStack.addLast(currentString.toString());
                currentNumber = 0;
                currentString = new StringBuilder();
            } else if (c == ']') {
                // 遇到右括号，进行字符串重复拼接
                StringBuilder temp = new StringBuilder();
                int repeatCount = repeatCountStack.removeLast();

                // 重复指定次数
                for (int i = 0; i < repeatCount; i++) {
                    temp.append(currentString);
                }

                // 与之前的结果合并
                currentString = new StringBuilder(resultStack.removeLast() + temp);
            } else if (Character.isDigit(c)) {
                // 累积计算数字
                currentNumber = currentNumber * 10 + (c - '0');
            } else {
                // 普通字符直接追加
                currentString.append(c);
            }
        }

        return currentString.toString();
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        String[] testCases = {
                "3[a]2[bc]", // 期望输出：aaabcbc
                "2[abc]3[cd]ef", // 期望输出：abcabccdcdcdef
                "abc3[cd]xyz" // 期望输出：abccdcdcdxyz
        };

        // 执行测试
        for (String test : testCases) {
            String result = decode(test);
            System.out.printf("输入：%s%n输出：%s%n%n", test, result);
        }
    }
}